package leetcode;

import java.util.HashMap;

public class NumberOfBoomerangs {

	/**
	 * O(n^3)的方法
	 */
	public int numberOfBoomerangs(int[][] points) {
		if (points == null) {
			return 0;
		}
		int count = 0;
		long distance = 0;
		long distance2 = 0;
		// O(n^3)的方法，遍历每个点，获得距离，然后找到下一个与该距离相等的点
		// 但是会TLE，怎么使用HashMap来加速这一过程呢
		for (int i = 0; i < points.length; i++) {
			int x = points[i][0];
			int y = points[i][1];
			for (int j = 0; j < points.length; j++) {
				if (j == i) {
					continue;
				}
				int x1 = points[j][0];
				int y1 = points[j][1];
				distance = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
				for (int k = 0; k < points.length; k++) {
					if (k == i || k == j) {
						continue;
					}
					int x2 = points[k][0];
					int y2 = points[k][1];
					distance2 = (x2 - x) * (x2 - x) + (y2 - y) * (y2 - y);
					if (distance2 == distance) {
						count++;
					}
				}
			}
		}

		return count;
	}

	// 使用map来加速至O(n^2)
	public int numberOfBoomerangs2(int[][] points) {
		if (points == null) {
			return 0;
		}
		int count = 0;
		HashMap<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < points.length; i++) {
			for (int j = 0; j < points.length; j++) {
				if (j == i) {
					continue;
				}
				int d = (int) getDistance(points[i], points[j]);
				map.put(d, map.getOrDefault(d, 0) + 1);
			}

			// 由于顺序不同也算不同的tuple，所以需要计算排列数，总数为val(表示该距离点的个数)，取2，
			//所以是val * (val - 1);
			for (int val : map.values()) {
				count += val * (val - 1);
			}
			map.clear();
		}
		return count;
	}

	public long getDistance(int[] point1, int[] point2) {
		int x = point1[0];
		int y = point1[1];
		int x1 = point2[0];
		int y1 = point2[1];
		return (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
	}
}
